package com.xgh.offer;

import java.util.Arrays;

/**
 * @ClassName Offer40
 * @Description
 * @Author xinggh
 * @Date 2020/7/1 22:11
 * @Version 1.0
 **/
public class Offer40 {
    /**
     * 剑指 Offer 40. 最小的k个数
     * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：arr = [3,2,1], k = 2
     * 输出：[1,2] 或者 [2,1]
     * 示例 2：
     * <p>
     * 输入：arr = [0,1,2,1], k = 1
     * 输出：[0]
     * <p>
     * <p>
     * 限制：
     * <p>
     * 0 <= k <= arr.length <= 10000
     * 0 <= arr[i] <= 10000
     */

    public int[] getLeastNumbers(int[] arr, int k) {

        if (arr.length == 0 || k == 0) {
            return new int[0];
        }
        //快速排序
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);
    }


    public static void quickSort(int arr[], int start, int end) {

        if (start >= end) {
            return;
        }
        int l = start;
        int r = end;
        int key = arr[start];
        while (l < r) {
            while (l < r && arr[r] >= key) {
                r--;
            }

            if (l < r) {
                arr[l] = arr[r];
            }

            while (l < r && arr[l] <= key) {
                l++;
            }
            if (l < r) {
                arr[r] = arr[l];
            }

        }
        arr[l] = key;
        quickSort(arr, start, l - 1);
        quickSort(arr, l + 1, end);
    }

    public static void main(String[] args) {
        int arr[] = {1, 4, 3, 2, 5};
        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.println(i);
        }
    }
}
